package srcLongestCommonSubsequence;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class LongestCommonSubsequence
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        String firstSequence = "ocurranec";
        String secondSequence = "occurrence";

        LongestCommonSubsequence lcs = new LongestCommonSubsequence(firstSequence, secondSequence);

        String commonSubsequence = lcs.ComputeLCSUsingDivideAndConquer();

        System.out.println(
                String.format(
                        "LCS of \n%s \n%s \nIS \n%s",
                        firstSequence,
                        secondSequence,
                        commonSubsequence));
    }
    String firstSequence;
    String secondSequence;

    List<Integer> lcsIndexes;

    public LongestCommonSubsequence(String firstSequence, String secondSequence)
    {
        this.firstSequence = firstSequence;
        this.secondSequence = secondSequence;
        this.lcsIndexes = new ArrayList<Integer>();
    }

    private String ComputeLCSUsingDivideAndConquer()
    {
        return ComputeLCSUsingDivideAndConquerRecursive(
                this.firstSequence.length(),
                this.secondSequence.length(),
                this.firstSequence,
                this.secondSequence);
    }

    private String ComputeLCSUsingDivideAndConquerRecursive(
            int m,
            int n,
            String firstSequence,
            String secondSequence)
    {
        String curLCS = "";

        if (n == 0)
        {
            curLCS = "";
        }
        else if (m == 1)
        {
            for (int j = 0; j < n; ++j)
            {
                if (firstSequence.charAt(0) == secondSequence.charAt(j))
                {
                    curLCS = Character.toString(firstSequence.charAt(0));
                }
                else
                {
                    curLCS = "";
                }
            }

        }
        else
        {
            int firstSeqMid = m/2;

            int[] leftColumn = this.GetColumnUsingForwardSpaceEfficientLCSAlgo(
                    firstSequence.substring(0, firstSeqMid),
                    secondSequence);

            int[] rightColumn = this.GetColumnUsingBackwardSpaceEfficientLCSAlgo(
                    firstSequence.substring(firstSeqMid),
                    secondSequence);

            int maximizingIndex = GetMaximizingIndex(leftColumn, rightColumn) - 1;

            String leftLCS = ComputeLCSUsingDivideAndConquerRecursive(
                    firstSeqMid,
                    maximizingIndex,
                    firstSequence.substring(0, firstSeqMid),
                    secondSequence.substring(0, maximizingIndex));

            String rightLCS = ComputeLCSUsingDivideAndConquerRecursive(
                    m - firstSeqMid,
                    n - maximizingIndex,
                    firstSequence.substring(firstSeqMid),
                    secondSequence.substring(maximizingIndex));

            curLCS = leftLCS + rightLCS;
        }

        return curLCS;
    }

    private String ComputeSolutionFromLCSIndexes(String secondSequence, List<Integer> lcsIndexes)
    {
        Collections.sort(lcsIndexes);
        StringBuffer stringBuf = new StringBuffer();

        for (int i = 0; i < lcsIndexes.size(); ++i)
        {
            stringBuf.append(secondSequence.charAt(lcsIndexes.get(i)));
        }

        return stringBuf.toString();
    }

    /**
     * Computes LCS by traversing strings from end to start.
     * Populates the optimal matrix column by column, starting from right most column,
     * but stores only current and previous columns to save space.
     * @param firstString
     * @param secondString
     * @return returns last column of computation
     */
    private int[] GetColumnUsingBackwardSpaceEfficientLCSAlgo(String firstString, String secondString)
    {
        int numFields = secondString.length() + 1;

        int[] prevIterationColumn = new int[numFields];
        int[] currentIterationColumn = new int[numFields];

        // Initialize values for base case to 0
        for (int j = numFields - 1; j >= 0; --j)
        {
            prevIterationColumn[j] = 0;
        }

        for (int i = firstString.length() - 1; i >= 0; --i)
        {
            currentIterationColumn[numFields - 1] = 0; // since this is entry corresponding to last column in matrix

            for (int j = secondString.length() - 1; j >= 0; --j)
            {
                if (secondString.charAt(j) == firstString.charAt(i))
                {
                    currentIterationColumn[j] = 1 + prevIterationColumn[j + 1];
                }
                else
                {
                    currentIterationColumn[j] = Math.max(prevIterationColumn[j], currentIterationColumn[j + 1]);
                }
            }

            // move values from currentIterationRow, to previousIterationRow to make space for next iteration
            for (int k = 0; k < numFields; ++k)
            {
                prevIterationColumn[k] = currentIterationColumn[k];
            }
        }

        return currentIterationColumn;
    }

    /**
     * Computes LCS by traversing strings from start to end.
     * Populates the optimal matrix column by column, starting from left most column,
     * but stores only current and previous columns to save space.
     * @param firstString
     * @param secondString
     * @return returns the last column of computation
     */
    private int[] GetColumnUsingForwardSpaceEfficientLCSAlgo(String firstString, String secondString)
    {
        int numFields = secondString.length() + 1;

        int[] previousIterationColumn = new int [numFields];
        int[] currentIterationColumn = new int [numFields];

        // Initialize values for base case to 0
        for (int j = 0; j < numFields; ++j)
        {
            previousIterationColumn[j] = 0;
        }

        for (int n = 1; n < firstString.length() + 1; ++n)
        {
            currentIterationColumn[0] = 0; // since this corresponds to first row entry in matrix

            for (int m = 1; m < secondString.length() + 1; ++m)
            {
                if (firstString.charAt(n - 1) == secondString.charAt(m - 1))
                {
                    currentIterationColumn[m] = 1 + previousIterationColumn[m - 1];
                }
                else
                {
                    currentIterationColumn[m] = Math.max(previousIterationColumn[m], currentIterationColumn[m - 1]);
                }
            }

            // move values from currentIterationColumn, to previousIterationColumn to make space for next iteration
            for (int k = 0; k < numFields; ++k)
            {
                previousIterationColumn[k] = currentIterationColumn[k];
            }
        }

        return currentIterationColumn;
    }

    private int GetMaximizingIndex(int[] leftColumn, int[] rightColumn)
    {
        if (leftColumn.length != rightColumn.length)
        {
            throw new IllegalArgumentException(
                    String.format(
                            "feftColumn.length (%d) and rightColumn.length (%d) should be the same!",
                            leftColumn.length,
                            rightColumn.length));
        }

        int maxSum = 0;
        int maxSumIndex = 0;
        int totalLength = leftColumn.length;

        for (int i = 0; i < totalLength; ++i)
        {
            int currentSum = leftColumn[i] + rightColumn[totalLength - 1 - i];
            if (currentSum >= maxSum)
            {
                maxSum = currentSum;
                maxSumIndex = i;
            }
        }

        return maxSumIndex;
    }

}
